{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Relative Loss After Buying Chocolates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumRelativeLosses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #购买巧克力后的最小相对损失"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现给定一个整数数组 <code>prices</code>，表示巧克力的价格；以及一个二维整数数组 <code>queries</code>，其中 <code>queries[i] = [ki, mi]</code>。</p>\n",
    "\n",
    "<p>Alice 和 Bob 去买巧克力，Alice 提出了一种付款方式，而 Bob 同意了。</p>\n",
    "\n",
    "<p>对于每个 <code>queries[i]</code> ，它的条件如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果一块巧克力的价格 <strong>小于等于</strong> <code>ki</code>，那么 Bob 为它付款。</li>\n",
    "\t<li>否则，Bob 为其中 <code>ki</code> 部分付款，而 Alice 为 <strong>剩余</strong> 部分付款。</li>\n",
    "</ul>\n",
    "\n",
    "<p>Bob 想要选择 <strong>恰好</strong> <code>mi</code> 块巧克力，使得他的 <strong>相对损失最小</strong> 。更具体地说，如果总共 Alice 付款了 <code>ai</code>，Bob 付款了 <code>bi</code>，那么 Bob 希望最小化 <code>bi - ai</code>。</p>\n",
    "\n",
    "<p>返回一个整数数组 <code>ans</code>，其中 <code>ans[i]</code> 是 Bob 在&nbsp;<code>queries[i]</code> 中可能的 <strong>最小相对损失</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>prices = [1,9,22,10,19], queries = [[18,4],[5,2]]\n",
    "<b>输出：</b>[34,-21]\n",
    "<b>解释：</b>对于第一个 query，Bob 选择价格为 [1,9,10,22] 的巧克力。他付了 1 + 9 + 10 + 18 = 38，Alice 付了 0 + 0 + 0 + 4 = 4。因此，Bob 的相对损失是 38 - 4 = 34。\n",
    "对于第二个 query，Bob 选择价格为 [19,22] 的巧克力。他付了 5 + 5 = 10，Alice 付了 14 + 17 = 31。因此，Bob 的相对损失是 10 - 31 = -21。\n",
    "可以证明这些是可能的最小相对损失。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>prices = [1,5,4,3,7,11,9], queries = [[5,4],[5,7],[7,3],[4,5]]\n",
    "<b>输出：</b>[4,16,7,1]\n",
    "<b>解释：</b>对于第一个 query，Bob 选择价格为 [1,3,9,11] 的巧克力。他付了 1 + 3 + 5 + 5 = 14，Alice 付了 0 + 0 + 4 + 6 = 10。因此，Bob 的相对损失是 14 - 10 = 4。\n",
    "对于第二个 query，Bob 必须选择所有的巧克力。他付了 1 + 5 + 4 + 3 + 5 + 5 + 5 = 28，Alice 付了 0 + 0 + 0 + 0 + 2 + 6 + 4 = 12。因此，Bob 的相对损失是 28 - 12 = 16。\n",
    "对于第三个 query，Bob 选择价格为 [1,3,11] 的巧克力。他付了 1 + 3 + 7 = 11，Alice 付了 0 + 0 + 4 = 4。因此，Bob 的相对损失是 11 - 4 = 7。\n",
    "对于第四个 query，Bob 选择价格为 [1,3,7,9,11] 的巧克力。他付了 1 + 3 + 4 + 4 + 4 = 16，Alice 付了 0 + 0 + 3 + 5 + 7 = 15。因此，Bob 的相对损失是 16 - 15 = 1。\n",
    "可以证明这些是可能的最小相对损失。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>prices = [5,6,7], queries = [[10,1],[5,3],[3,3]]\n",
    "<b>输出：</b>[5,12,0]\n",
    "<b>解释：</b>对于第一个 query，Bob 选择价格为 5 的巧克力。他付了 5，Alice 付了 0。因此，Bob 的相对损失是 5 - 0 = 5。\n",
    "对于第二个 query，Bob 必须选择所有的巧克力。他付了 5 + 5 + 5 = 15，Alice 付了 0 + 1 + 2 = 3。因此，Bob 的相对损失是 15 - 3 = 12。\n",
    "对于第三个 query，Bob 必须选择所有的巧克力。他付了 3 + 3 + 3 = 9，Alice 付了 2 + 3 + 4 = 9。因此，Bob 的相对损失是 9 - 9 = 0。\n",
    "可以证明这些是可能的最小相对损失。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= prices.length == n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= prices[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>queries[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= k<sub>i</sub> &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= m<sub>i</sub> &lt;= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-relative-loss-after-buying-chocolates](https://leetcode.cn/problems/minimum-relative-loss-after-buying-chocolates/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-relative-loss-after-buying-chocolates](https://leetcode.cn/problems/minimum-relative-loss-after-buying-chocolates/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,9,22,10,19]\\n[[18,4],[5,2]]', '[1,5,4,3,7,11,9]\\n[[5,4],[5,7],[7,3],[4,5]]', '[5,6,7]\\n[[10,1],[5,3],[3,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        def f(k: int, m: int) -> int:\n",
    "            l, r = 0, min(m, bisect_right(prices, k))\n",
    "            while l < r:\n",
    "                mid = (l + r) >> 1\n",
    "                right = m - mid\n",
    "                if prices[mid] >= 2 * k - prices[n - right]:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return l\n",
    "\n",
    "        prices.sort()\n",
    "        s = list(accumulate(prices, initial=0))\n",
    "        ans = []\n",
    "        n = len(prices)\n",
    "        for k, m in queries:\n",
    "            l = f(k, m)\n",
    "            r = m - l\n",
    "            loss = s[l] + 2 * k * r - (s[n] - s[n - r])\n",
    "            ans.append(loss)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(prices)\n",
    "        prices.sort()\n",
    "        pre = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            pre[i + 1] = pre[i] + prices[i]\n",
    "\n",
    "        def calc(pre_len: int) -> int:\n",
    "            suf_len = m - pre_len\n",
    "            return pre[pre_len] + 2 * k * suf_len - (pre[n] - pre[n - suf_len])\n",
    "        \n",
    "        # 三分法求严格凸函数 fn 在 [lower, upper] 闭区间内的最小值\n",
    "        def minimize(fn: Callable, lower: int, upper: int) -> int:\n",
    "            ans = inf\n",
    "            while upper - lower >= 3:\n",
    "                diff = upper - lower\n",
    "                mid1 = lower + diff // 3\n",
    "                mid2 = lower + 2 * diff // 3\n",
    "                if fn(mid1) > fn(mid2):\n",
    "                    lower = mid1\n",
    "                else:\n",
    "                    upper = mid2\n",
    "            while lower <= upper:\n",
    "                ans = min(ans, fn(lower))\n",
    "                lower += 1\n",
    "            return ans\n",
    "        \n",
    "        ans = []\n",
    "        for k, m in queries:\n",
    "            ans.append(minimize(calc, 0, m))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        def f(k: int, m: int) -> int:\n",
    "            l, r = 0, min(m, bisect_right(prices, k))\n",
    "            while l < r:\n",
    "                mid = (l + r) >> 1\n",
    "                right = m - mid\n",
    "                if prices[mid] < 2 * k - prices[n - right]:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid\n",
    "            return l\n",
    "\n",
    "        prices.sort()\n",
    "        s = list(accumulate(prices, initial=0))\n",
    "        ans = []\n",
    "        n = len(prices)\n",
    "        for k, m in queries:\n",
    "            l = f(k, m)\n",
    "            r = m - l\n",
    "            loss = s[l] + 2 * k * r - (s[n] - s[n - r])\n",
    "            ans.append(loss)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(prices)\n",
    "        prices.sort()\n",
    "        pre = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            pre[i + 1] = pre[i] + prices[i]\n",
    "\n",
    "        def calc(pre_len: int) -> int:\n",
    "            suf_len = m - pre_len\n",
    "            return pre[pre_len] + 2 * k * suf_len - (pre[n] - pre[n - suf_len])\n",
    "        \n",
    "        def minimize(f: Callable, lower: int, upper: int) -> int:\n",
    "            while upper - lower >= 3:\n",
    "                diff = upper - lower\n",
    "                mid1 = lower + diff // 3\n",
    "                mid2 = lower + 2 * diff // 3\n",
    "                if f(mid1) > f(mid2):\n",
    "                    lower = mid1\n",
    "                else:\n",
    "                    upper = mid2\n",
    "            res = inf\n",
    "            while lower <= upper:\n",
    "                res = min(res, f(lower))\n",
    "                lower += 1\n",
    "            return res\n",
    "        \n",
    "        ans = []\n",
    "        for k, m in queries:\n",
    "            ans.append(minimize(calc, 0, m))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        prices.sort()\n",
    "\n",
    "        n = len(prices)\n",
    "        pre = prices[:]\n",
    "        for j in range(1,n):\n",
    "            pre[j]+=pre[j-1]\n",
    "        def calc(l,r):\n",
    "            if l>r: return 0\n",
    "            return pre[r]-pre[l-1] if l else pre[r]\n",
    "        \n",
    "        def check(m,q,xmax,cnt):\n",
    "            return 0 if m==xmax or 2*q-prices[cnt-m-1]-prices[n-m-1]>0 else -1\n",
    "\n",
    "        res = []\n",
    "        for q,cnt in queries:\n",
    "            p1 = bisect_left(prices,q)\n",
    "            xmax = min(cnt,n-p1)\n",
    "            xmin = max(0,cnt-p1)\n",
    "            cur = bisect_left(range(xmin,xmax+1),0,key=lambda x:check(x,q,xmax,cnt))+xmin\n",
    "            res.append(calc(0,cnt-cur-1)+2*cur*q-calc(n-cur,n-1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        prices.sort()\n",
    "\n",
    "        n = len(prices)\n",
    "        pre = prices[:]\n",
    "        for j in range(1,n):\n",
    "            pre[j]+=pre[j-1]\n",
    "        def calc(l,r):\n",
    "            if l>r: return 0\n",
    "            return pre[r]-pre[l-1] if l else pre[r]\n",
    "        \n",
    "        def check(m,q,xmx):\n",
    "            if m==xmx:\n",
    "                return False\n",
    "            cur1 = calc(0,cnt-m-1)+2*m*q-calc(n-m,n-1)\n",
    "            cur2 = calc(0,cnt-m-2)+2*(m+1)*q-calc(n-m-1,n-1)\n",
    "            return cur2<cur1\n",
    "\n",
    "        res = []\n",
    "        for q,cnt in queries:\n",
    "            p1 = bisect_left(prices,q)\n",
    "            xmax = min(cnt,n-p1)\n",
    "            xmin = max(0,cnt-p1)\n",
    "\n",
    "            l = xmin\n",
    "            r = xmax\n",
    "            while r>l:\n",
    "                m = (l+r)//2\n",
    "                if check(m,q,xmax):\n",
    "                    l = m+1\n",
    "                else:\n",
    "                    r = m\n",
    "            res.append(calc(0,cnt-l-1)+2*l*q-calc(n-l,n-1))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        prices.sort()\n",
    "        n = len(prices)\n",
    "        s = list(accumulate(prices, initial=0))\n",
    "        def getsum(l, r):\n",
    "            return s[r] - s[l]\n",
    "        ret = []\n",
    "        for k, m in queries:\n",
    "            p = bisect_left(prices, k)\n",
    "            # l, r = 0, min(m, p)\n",
    "            l, r = max(0, p + m - n), min(m, p)\n",
    "            # while l < r:\n",
    "            #     mid = (l+r) // 2\n",
    "            #     i = n-(m-mid)\n",
    "            #     if i < p or prices[mid] <= 2*k - prices[i]:\n",
    "            #         l = mid + 1\n",
    "            #     else:\n",
    "            #         r = mid\n",
    "            l = bisect_left(range(l, r), True, key=lambda t: prices[t] + prices[n - m + t] > 2 * k) + l\n",
    "            cur = getsum(0, l) + 2 * (m - l) * k - getsum(n - (m - l), n)\n",
    "            ret.append(cur)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        def g(x,m,k):\n",
    "            return has[-1] - has[x+1] - has[x-n+m] - 2*k*x\n",
    "        prices.sort()\n",
    "        n = len(prices)\n",
    "        has = [0]\n",
    "        for i in prices:\n",
    "            has.append(has[-1]+i)\n",
    "        res = []\n",
    "        for k, m in queries:\n",
    "            b = bisect.bisect(prices, k)\n",
    "            if m == n:\n",
    "                res.append(2 * has[b] - has[-1] + 2 * (n-b) * k)\n",
    "            else:    \n",
    "                l, r = 0, min(b, m)\n",
    "                while l < r:\n",
    "                    mid = (l + r) // 2\n",
    "                    if prices[mid] < 2 * k - prices[n - m + mid]:\n",
    "                        l = mid + 1\n",
    "                    else:\n",
    "                        r = mid\n",
    "                tep = has[l] + has[n - m + l] - has[-1] + 2 * k * (m - l)\n",
    "                if l:\n",
    "                    l -= 1\n",
    "                    tep = min(tep, has[l] + has[n - m + l] - has[-1] + 2 * k * (m - l))\n",
    "                res.append(tep)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(prices)\n",
    "        prices.sort()\n",
    "        preSum = list(itertools.accumulate(prices))\n",
    "        sufSum = list(itertools.accumulate(prices[::-1]))[::-1]\n",
    "        res = [0] * len(queries)\n",
    "\n",
    "        def helper(a, b):\n",
    "            left, right = 0, b\n",
    "            while left <= right:\n",
    "                mid = left + right >> 1\n",
    "                if a - prices[mid] > (float(\"inf\") if mid == b else prices[mid + n - b]) - a:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            return left\n",
    "        \n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            idx = helper(a, b)\n",
    "            left = idx * a - (preSum[idx - 1] if idx else 0)\n",
    "            right = (sufSum[idx + n - b] if idx != b else 0) - (b - idx) * a\n",
    "            res[i] = a * b - (left + right)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(prices)\n",
    "        prices.sort()\n",
    "        preSum = list(itertools.accumulate(prices))\n",
    "        sufSum = list(itertools.accumulate(prices[::-1]))[::-1]\n",
    "        res = [0] * len(queries)\n",
    "\n",
    "        def helper(k, m):\n",
    "            left, right = 0, m\n",
    "            while left <= right:\n",
    "                mid = left + right >> 1\n",
    "                if k - prices[mid] > (float(\"inf\") if mid == m else prices[mid + n - m]) - k:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            return left\n",
    "        \n",
    "        for i, (k, m) in enumerate(queries):\n",
    "            idx = helper(k, m)\n",
    "            left = idx * k - (preSum[idx - 1] if idx else 0)\n",
    "            right = (sufSum[idx + n - m] if idx != m else 0) - (m - idx) * k\n",
    "            res[i] = k * m - (left + right)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        prices.sort()\n",
    "        print(prices)\n",
    "        n = len(prices)\n",
    "        s = [0] * n\n",
    "        s[0] = prices[0]\n",
    "        for i in range(1,n):\n",
    "            s[i] = s[i-1] + prices[i]\n",
    "        def getsum(i, j):\n",
    "            res = s[j]\n",
    "            if i:\n",
    "                res -= s[i-1]\n",
    "            return res\n",
    "        ret = []\n",
    "        for k, m in queries:\n",
    "            sp = bisect_left(prices, k)\n",
    "            l, r = 0, min(m, sp)\n",
    "            while l < r:\n",
    "                mid = (l+r) // 2\n",
    "                i = n-(m-mid)\n",
    "                if i < sp or prices[mid] <= 2*k - prices[i]:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid\n",
    "            cur = 0\n",
    "            if l:\n",
    "                cur += getsum(0, l-1)\n",
    "            if m-l:\n",
    "                cur += 2*(m-l)*k - getsum(n-(m-l), n-1)\n",
    "            ret.append(cur)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(prices)\n",
    "        prices.sort()\n",
    "        prefix = [0]\n",
    "        for p in prices:\n",
    "            prefix.append(prefix[-1]+p)\n",
    "        res = []\n",
    "        for q,cnt in queries:\n",
    "            ii = bisect.bisect_left(prices, q)\n",
    "            def score(l_cnt):\n",
    "                if l_cnt>cnt: return math.inf\n",
    "                l_score = prefix[l_cnt]\n",
    "                r_cnt = cnt-l_cnt\n",
    "                r_score = 2*q*r_cnt - (prefix[-1]-prefix[n-r_cnt])\n",
    "                return l_score + r_score\n",
    "            lo,hi = 0,min(cnt,ii)\n",
    "            while lo<=hi:\n",
    "                mid = (lo+hi)//2\n",
    "                if score(mid)<=score(mid+1):\n",
    "                    hi = mid - 1\n",
    "                else:\n",
    "                    lo = mid + 1\n",
    "            res.append(score(lo))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "from typing import List\n",
    "from typing import Callable, Tuple\n",
    "\n",
    "\n",
    "INF = int(1e18)\n",
    "\n",
    "\n",
    "def fibonacciSearch(f: Callable[[int], int], start: int, end: int, min: bool) -> Tuple[int, int]:\n",
    "    \"\"\"斐波那契搜索寻找[start,end)中的一个极值点,不要求单峰性质.\n",
    "    Args:\n",
    "        f: 目标函数.\n",
    "        start: 搜索区间左端点(包含).\n",
    "        end: 搜索区间右端点(不包含).\n",
    "        min: 是否寻找最小值.\n",
    "    Returns:\n",
    "        极值点的横坐标x和纵坐标f(x).\n",
    "    \"\"\"\n",
    "    assert start < end\n",
    "    end -= 1\n",
    "    a, b, c, d = start, start + 1, start + 2, start + 3\n",
    "    n = 0\n",
    "    while d < end:\n",
    "        b = c\n",
    "        c = d\n",
    "        d = b + c - a\n",
    "        n += 1\n",
    "\n",
    "    def get(i: int) -> int:\n",
    "        if end < i:\n",
    "            return INF\n",
    "        return f(i) if min else -f(i)\n",
    "\n",
    "    ya, yb, yc, yd = get(a), get(b), get(c), get(d)\n",
    "    for _ in range(n):\n",
    "        if yb < yc:\n",
    "            d = c\n",
    "            c = b\n",
    "            b = a + d - c\n",
    "            yd = yc\n",
    "            yc = yb\n",
    "            yb = get(b)\n",
    "        else:\n",
    "            a = b\n",
    "            b = c\n",
    "            c = a + d - b\n",
    "            ya = yb\n",
    "            yb = yc\n",
    "            yc = get(c)\n",
    "\n",
    "    x = a\n",
    "    y = ya\n",
    "    if yb < y:\n",
    "        x = b\n",
    "        y = yb\n",
    "    if yc < y:\n",
    "        x = c\n",
    "        y = yc\n",
    "    if yd < y:\n",
    "        x = d\n",
    "        y = yd\n",
    "\n",
    "    return (x, y) if min else (x, -y)\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        def fun(preLen: int) -> int:\n",
    "            \"\"\"从prices的前缀中选择preLen个数时,损失的最小值.\"\"\"\n",
    "            sufLen = count - preLen\n",
    "            return preSum[preLen] + (2 * threshold * sufLen - sufSum[sufLen])\n",
    "\n",
    "        prices.sort()\n",
    "        preSum = [0] + list(accumulate(prices))\n",
    "        sufSum = [0] + list(accumulate(prices[::-1]))\n",
    "        res = [0] * len(queries)\n",
    "        for i, (threshold, count) in enumerate(queries):\n",
    "            res[i] = fibonacciSearch(fun, 0, count+1, min=True)[1]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        def fun(preLen: int) -> int:\n",
    "            \"\"\"从prices的前缀中选择preLen个数时,损失的最小值.\"\"\"\n",
    "            sufLen = count - preLen\n",
    "            return preSum[preLen] + (2 * threshold * sufLen - sufSum[sufLen])\n",
    "\n",
    "        def minimize(func, lo, hi):\n",
    "            while lo < hi:\n",
    "                m1 = lo+(hi-lo)//3\n",
    "                m2 = hi-(hi-lo)//3\n",
    "                if func(m1) >= func(m2):\n",
    "                    lo = m1+1\n",
    "                else:\n",
    "                    hi = m2-1\n",
    "            return func(lo) \n",
    "\n",
    "\n",
    "        prices.sort()\n",
    "        preSum = [0] + list(accumulate(prices))\n",
    "        sufSum = [0] + list(accumulate(prices[::-1]))\n",
    "        res = [0] * len(queries)\n",
    "        for i, (threshold, count) in enumerate(queries):\n",
    "            res[i] = minimize(fun, 0, count)\n",
    "        return res\n",
    "\n",
    "# 作者：草莓奶昔\\U0001f353\n",
    "# 链接：https://leetcode.cn/problems/minimum-relative-loss-after-buying-chocolates/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        def fun(k: int) -> int:\n",
    "            \"\"\"从prices的前缀中选择k个数时,损失的最小值.\"\"\"\n",
    "            sufLen = count - k\n",
    "            return preSum[k] + (2 * threshold * sufLen - sufSum[sufLen])\n",
    "\n",
    "        prices.sort()\n",
    "        preSum = [0] + list(accumulate(prices))\n",
    "        sufSum = [0] + list(accumulate(prices[::-1]))\n",
    "        res = [0] * len(queries)\n",
    "        for i, (threshold, count) in enumerate(queries):\n",
    "            res[i] = minimize(fun, 0, count)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "INF = int(4e18)\n",
    "\n",
    "def minimize(fun: Callable[[int], int], lower: int, upper: int) -> int:\n",
    "    \"\"\"三分法求`严格凸函数fun`在`[lower,upper]`间的最小值\"\"\"\n",
    "    res = INF\n",
    "    while (upper - lower) >= 3:\n",
    "        diff = upper - lower\n",
    "        mid1 = lower + diff // 3\n",
    "        mid2 = lower + 2 * diff // 3\n",
    "        if fun(mid1) > fun(mid2):\n",
    "            lower = mid1\n",
    "        else:\n",
    "            upper = mid2\n",
    "\n",
    "    while lower <= upper:\n",
    "        cand = fun(lower)\n",
    "        res = cand if cand < res else res\n",
    "        lower += 1\n",
    "\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        def fun(preLen: int) -> int:\n",
    "            \"\"\"从prices的前缀中选择preLen个数时,损失的最小值.\"\"\"\n",
    "            sufLen = count - preLen\n",
    "            return preSum[preLen] + (2 * threshold * sufLen - sufSum[sufLen])\n",
    "\n",
    "        prices.sort()\n",
    "        preSum = [0] + list(accumulate(prices))\n",
    "        sufSum = [0] + list(accumulate(prices[::-1]))\n",
    "        res = [0] * len(queries)\n",
    "        for i, (threshold, count) in enumerate(queries):\n",
    "            res[i] = minimize(fun, 0, count)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "INF = int(4e18)\n",
    "\n",
    "def minimize(fun: Callable[[int], int], lower: int, upper: int) -> int:\n",
    "    \"\"\"三分法求`严格凸函数fun`在`[lower,upper]`间的最小值\"\"\"\n",
    "    res = INF\n",
    "    while (upper - lower) >= 3:\n",
    "        diff = upper - lower\n",
    "        mid1 = lower + diff // 3\n",
    "        mid2 = lower + 2 * diff // 3\n",
    "        if fun(mid1) > fun(mid2):\n",
    "            lower = mid1\n",
    "        else:\n",
    "            upper = mid2\n",
    "\n",
    "    while lower <= upper:\n",
    "        cand = fun(lower)\n",
    "        res = cand if cand < res else res\n",
    "        lower += 1\n",
    "\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        def fun(preLen: int) -> int:\n",
    "            \"\"\"从prices的前缀中选择preLen个数时,损失的最小值.\"\"\"\n",
    "            sufLen = count - preLen\n",
    "            return preSum[preLen] + (2 * threshold * sufLen - sufSum[sufLen])\n",
    "\n",
    "        prices.sort()\n",
    "        preSum = [0] + list(accumulate(prices))\n",
    "        sufSum = [0] + list(accumulate(prices[::-1]))\n",
    "        res = [0] * len(queries)\n",
    "        for i, (threshold, count) in enumerate(queries):\n",
    "            res[i] = minimize(fun, 0, count)\n",
    "        return res\n",
    "\n",
    "INF = int(4e18)\n",
    "\n",
    "def minimize(fun: Callable[[int], int], lower: int, upper: int) -> int:\n",
    "    \"\"\"三分法求`严格凸函数fun`在`[lower,upper]`间的最小值\"\"\"\n",
    "    res = INF\n",
    "    while (upper - lower) >= 3:\n",
    "        diff = upper - lower\n",
    "        mid1 = lower + diff // 3\n",
    "        mid2 = lower + 2 * diff // 3\n",
    "        if fun(mid1) > fun(mid2):\n",
    "            lower = mid1\n",
    "        else:\n",
    "            upper = mid2\n",
    "    while lower <= upper:\n",
    "        cand = fun(lower)\n",
    "        res = cand if cand < res else res\n",
    "        lower += 1\n",
    "    return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "from typing import List\n",
    "from typing import Callable, Tuple\n",
    "\n",
    "\n",
    "INF = int(1e18)\n",
    "\n",
    "\n",
    "from typing import Callable, Tuple\n",
    "\n",
    "\n",
    "INF = int(1e18)\n",
    "\n",
    "\n",
    "def fibonacciSearch(f: Callable[[int], int], left: int, right: int, min: bool) -> Tuple[int, int]:\n",
    "    \"\"\"斐波那契搜索寻找[left,right]中的一个极值点,不要求单峰性质.\n",
    "    Args:\n",
    "        f: 目标函数.\n",
    "        left: 搜索区间左端点(包含).\n",
    "        right: 搜索区间右端点(包含).\n",
    "        min: 是否寻找最小值.\n",
    "    Returns:\n",
    "        极值点的横坐标x和纵坐标f(x).\n",
    "    \"\"\"\n",
    "    assert left <= right\n",
    "    a, b, c, d = left, left + 1, left + 2, left + 3\n",
    "    n = 0\n",
    "    while d < right:\n",
    "        b = c\n",
    "        c = d\n",
    "        d = b + c - a\n",
    "        n += 1\n",
    "\n",
    "    def get(i: int) -> int:\n",
    "        if right < i:\n",
    "            return INF\n",
    "        return f(i) if min else -f(i)\n",
    "\n",
    "    ya, yb, yc, yd = get(a), get(b), get(c), get(d)\n",
    "    for _ in range(n):\n",
    "        if yb < yc:\n",
    "            d = c\n",
    "            c = b\n",
    "            b = a + d - c\n",
    "            yd = yc\n",
    "            yc = yb\n",
    "            yb = get(b)\n",
    "        else:\n",
    "            a = b\n",
    "            b = c\n",
    "            c = a + d - b\n",
    "            ya = yb\n",
    "            yb = yc\n",
    "            yc = get(c)\n",
    "\n",
    "    x = a\n",
    "    y = ya\n",
    "    if yb < y:\n",
    "        x = b\n",
    "        y = yb\n",
    "    if yc < y:\n",
    "        x = c\n",
    "        y = yc\n",
    "    if yd < y:\n",
    "        x = d\n",
    "        y = yd\n",
    "\n",
    "    return (x, y) if min else (x, -y)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        def fun(preLen: int) -> int:\n",
    "            \"\"\"从prices的前缀中选择preLen个数时,损失的最小值.\"\"\"\n",
    "            sufLen = count - preLen\n",
    "            return preSum[preLen] + (2 * threshold * sufLen - sufSum[sufLen])\n",
    "\n",
    "        prices.sort()\n",
    "        preSum = [0] + list(accumulate(prices))\n",
    "        sufSum = [0] + list(accumulate(prices[::-1]))\n",
    "        res = [0] * len(queries)\n",
    "        for i, (threshold, count) in enumerate(queries):\n",
    "            res[i] = fibonacciSearch(fun, 0, count, min=True)[1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        q = sorted(queries)\n",
    "        ans = {}\n",
    "        less_list = []\n",
    "        more_list = []\n",
    "        for price in prices:\n",
    "            if price <= q[0][0]:\n",
    "                less_list.append(price)\n",
    "            else:\n",
    "                more_list.append(price)\n",
    "        less_list.sort()\n",
    "        more_list.sort(reverse=True)\n",
    "        less_sum = less_list.copy()\n",
    "        more_sum = more_list.copy()\n",
    "        for i in range(1, len(less_sum)):\n",
    "            less_sum[i] += less_sum[i - 1]\n",
    "        for i in range(1, len(more_sum)):\n",
    "            more_sum[i] += more_sum[i - 1]\n",
    "\n",
    "        def get_loss(less_n, more_n, b):\n",
    "            loss = 0\n",
    "            if less_n > 0:\n",
    "                loss += less_sum[less_n - 1]\n",
    "            if more_n > 0:\n",
    "                loss += 2 * b * more_n - more_sum[more_n - 1]\n",
    "            return loss\n",
    "\n",
    "        for bound, count in q:\n",
    "            while more_list and more_list[-1] <= bound:\n",
    "                less_list.append(more_list.pop())\n",
    "                if not less_sum:\n",
    "                    less_sum.append(less_list[-1])\n",
    "                else:\n",
    "                    less_sum.append(less_sum[-1] + less_list[-1])\n",
    "            left = less_min = max(0, count - len(more_list))\n",
    "            right = less_max = min(count, len(less_list))\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                less_num = mid\n",
    "                more_num = count - less_num\n",
    "                less_loss = less_list[max(0, less_num - 1)]\n",
    "                more_loss = 2 * bound - more_list[max(more_num - 1, 0)]\n",
    "                if less_loss <= more_loss:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            min_loss = get_loss(left, count - left, bound)\n",
    "            if left - 1 >= less_min:\n",
    "                min_loss = min(min_loss, get_loss(left - 1, count - left + 1, bound))\n",
    "            if left + 1 <= less_max:\n",
    "                min_loss = min(min_loss, get_loss(left + 1, count - left - 1, bound))\n",
    "            ans[(bound, count)] = min_loss\n",
    "        return [ans[(bound, count)] for bound, count in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        def fun(k: int) -> int:\n",
    "            \"\"\"从prices的前缀中选择k个数时,损失的最小值.\"\"\"\n",
    "            sufLen = count - k\n",
    "            return preSum[k] + (2 * threshold * sufLen - sufSum[sufLen])\n",
    "\n",
    "        prices.sort()\n",
    "        preSum = [0] + list(accumulate(prices))\n",
    "        sufSum = [0] + list(accumulate(prices[::-1]))\n",
    "        res = [0] * len(queries)\n",
    "        for i, (threshold, count) in enumerate(queries):\n",
    "            res[i] = minimize(fun, 0, count)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "INF = int(4e18)\n",
    "\n",
    "def minimize(fun: Callable[[int], int], lower: int, upper: int) -> int:\n",
    "    \"\"\"三分法求`严格凸函数fun`在`[lower,upper]`间的最小值\"\"\"\n",
    "    res = INF\n",
    "    while (upper - lower) >= 3:\n",
    "        diff = (upper - lower) // 3\n",
    "        mid1 = lower + diff\n",
    "        mid2 = upper - diff\n",
    "        if fun(mid1) > fun(mid2):\n",
    "            lower = mid1\n",
    "        else:\n",
    "            upper = mid2\n",
    "\n",
    "    while lower <= upper:\n",
    "        cand = fun(lower)\n",
    "        res = cand if cand < res else res\n",
    "        lower += 1\n",
    "\n",
    "    return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        def fun(k: int) -> int:\n",
    "            \"\"\"从prices的前缀中选择k个数时,损失的最小值.\"\"\"\n",
    "            sufLen = count - k\n",
    "            return preSum[k] + (2 * threshold * sufLen - sufSum[sufLen])\n",
    "\n",
    "        prices.sort()\n",
    "        preSum = [0] + list(accumulate(prices))\n",
    "        sufSum = [0] + list(accumulate(prices[::-1]))\n",
    "        res = [0] * len(queries)\n",
    "        for i, (threshold, count) in enumerate(queries):\n",
    "            res[i] = minimize(fun, 0, count)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "INF = int(4e18)\n",
    "\n",
    "def minimize(fun: Callable[[int], int], lower: int, upper: int) -> int:\n",
    "    \"\"\"三分法求`严格凸函数fun`在`[lower,upper]`间的最小值\"\"\"\n",
    "    res = INF\n",
    "    while (upper - lower) >= 3:\n",
    "        diff = upper - lower\n",
    "        mid1 = lower + diff // 3\n",
    "        mid2 = lower + 2 * diff // 3\n",
    "        if fun(mid1) > fun(mid2):\n",
    "            lower = mid1\n",
    "        else:\n",
    "            upper = mid2\n",
    "\n",
    "    while lower <= upper:\n",
    "        cand = fun(lower)\n",
    "        res = cand if cand < res else res\n",
    "        lower += 1\n",
    "\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "from typing import List\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumRelativeLosses(self, prices: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        def fun(k: int) -> int:\n",
    "            \"\"\"从prices的前缀中选择k个数时,损失的最小值.\"\"\"\n",
    "            sufLen = count - k\n",
    "            return preSum[k] + (2 * threshold * sufLen - sufSum[sufLen])\n",
    "\n",
    "        prices.sort()\n",
    "        preSum = [0] + list(accumulate(prices))\n",
    "        sufSum = [0] + list(accumulate(prices[::-1]))\n",
    "        res = [0] * len(queries)\n",
    "        for i, (threshold, count) in enumerate(queries):\n",
    "            res[i] = minimize(fun, 0, count)\n",
    "        return res\n",
    "\n",
    "from typing import Callable\n",
    "\n",
    "\n",
    "INF = int(4e18)\n",
    "\n",
    "\n",
    "def minimize(fun: Callable[[int], int], lower: int, upper: int) -> int:\n",
    "    \"\"\"三分法求`严格凸函数fun`在`[lower,upper]`间的最小值\"\"\"\n",
    "    res = INF\n",
    "    while (upper - lower) >= 3:\n",
    "        diff = upper - lower\n",
    "        mid1 = lower + diff // 3\n",
    "        mid2 = lower + 2 * diff // 3\n",
    "        if fun(mid1) > fun(mid2):\n",
    "            lower = mid1\n",
    "        else:\n",
    "            upper = mid2\n",
    "\n",
    "    while lower <= upper:\n",
    "        cand = fun(lower)\n",
    "        res = cand if cand < res else res\n",
    "        lower += 1\n",
    "\n",
    "    return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
